package com.nl.sort;

public class MoreThanHalfNum {

	public static int moreThanHalf(int[] nums) {

		int index = partition(nums, 0, nums.length - 1);
		int mid = nums.length >> 1;
		int start = 0;
		int end = nums.length - 1;
		while (index != mid) {
			if (index < mid) {
				start = index + 1;
			} else {
				end = index - 1;
			}
			index = partition(nums, start, end);
		}
		if(checkIsMoreThanHalf(nums,nums[mid])){
			return nums[mid];
		}

		return -1;

	}
	
	public static int moreThanHalf2(int[]nums){
		int times=0;
		int num=-1;
		for(int i=0;i<nums.length;i++){
			if(times==0){
				times=1;
				num=nums[i];
			}else if(num==nums[i]){
				times++;
			}else{
				times--;
			}
		}

		if(checkIsMoreThanHalf(nums,num)){
			return num;
		}

		return -1;
	}

	private static boolean checkIsMoreThanHalf(int[]nums,int num){
		int times = 0;
		for(int i=0;i<nums.length-1;i++){
			if(nums[i]==num){
				times++;
			}
		}
		if(times >nums.length>>1){
			return true;
		}
		return false;
	}
	private static int partition(int[] nums, int start, int end) {
		if (start == end) {
			return start;
		}
		int p = start;
		int left = start + 1, right = end;
		while (left < right) {
			while (left<right && nums[right] > nums[p]) {
				right--;
			}
			while (left <right && nums[left] < nums[p]) {
				left++;
			}
			if (left < right) {
				swap(nums, left, right);
				left++;
				right--;
			}
		}
		swap(nums, p, left);
		return left;
	}

	private static void swap(int[] nums, int left, int right) {
		int tmp = nums[left];
		nums[left] = nums[right];
		nums[right] = tmp;
	}
	public static void main(String[] args) {
		System.out.println(moreThanHalf(new int[]{1,2,4,5,6,4,4,4,4,4,4,10}));
		System.out.println(moreThanHalf2(new int[]{1,2,4,5,6,4,4,4,4,4,4,10}));
	}
}
